/*
 * @lc app=leetcode.cn id=971 lang=javascript
 *
 * [971] 翻转二叉树以匹配先序遍历
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number[]} voyage
 * @return {number[]}
 */


// var preOrder = function(root, voyage, ret, ind) {
//   if(!root) return true;
//   console.log(root, voyage)
//   if(voyage[ind] != root.val) return false;
//   ind++;
//   if(root.left && root.left.val != voyage[ind]){
//     [root.left, root.right] = [root.right, root.left];
//     ret.push(root.val);
//   }

//   if(!preOrder(root.left, voyage, ret, ind)) return false;
//   if(!preOrder(root.right, voyage, ret, ind)) return false;
//   return true;
// }

var flipMatchVoyage = function(root, voyage) {
  let ret = [], ind = 0;
  // ind 需要在回调中做修改，所以不能通过传参方式传递
  var preOrder = function(root, voyage, ret) {
    if(!root) return true;
    if(voyage[ind] != root.val) return false;
    ind++;
    if(root.left && root.left.val != voyage[ind]){
      [root.left, root.right] = [root.right, root.left];
      ret.push(root.val);
    }
  
    // ind 需要在left节点回调中增加 1 
    if(!preOrder(root.left, voyage, ret)) return false;

    // right节点回调中的ind 需要使用left中增加 1 后的值
    if(!preOrder(root.right, voyage, ret)) return false;
    return true;
  }

  let flag = preOrder(root, voyage, ret);
  return !flag ? [-1] : ret;
}

// @lc code=end

